Processor instructions sometimes include branch instructions, which branch to an indicated address. In current processors, instructions are executed using a pipeline structure.
Instruction execution in a pipeline proceeds by fetching the next instruction to be executed from a later address before the execution of a given instruction is complete. On occasion, the flow of a program will change due to execution of a branch instruction, rendering the fetched instruction unnecessary. For this reason, a new instruction must be fetched from the branch destination address to replace the now-unnecessary instruction.
Restarting the fetching of instructions in this way causes instruction processing that has already made progress down the pipeline to be aborted (what is known as a pipeline hazard), which is one cause of performance degradation in processors.
Hence branch destination prediction for branch instructions is critical to processors.
One type of branch prediction is conditional branch instruction. A conditional branch instruction involves determining whether or not branching will ensue from a branch instruction according to calculation results made at that time. Should branching not ensue, the succeeding instructions are executed. When branching does ensue, an instruction indicated by a fixed branch destination address is executed.
There is technology relating to conditional branch instructions for determining the branch destination by guessing whether or not branching will ensue according to past branch results. That is, statistics on whether or not branching occurred are collected from past branch results and the most probable branch destination is predicted accordingly. The reliability of branch prediction using conditional branch instruction can be improved accordingly.
However, there also exists a more complex form of branching known as indirect branching. Indirect branching involves cases in which the branch destination is not fixed, such as cases featuring instructions to branch to a value set by a given register, to branch according to address substitution in a program counter, and the like.
With indirect branching, not only is the occurrence of conditional branching uncertain, but the branch destination itself is not fixed, either. Therefore, the branch destination cannot be predicted through simple branch prediction functions.
One conventional technology for indirect branching prediction is the return stack. The return address after function execution varies according to function call origin, and so the function call origin address is recorded in a stack or similar structure in memory in order to be branched when returning from the function. This return address is saved in an exclusive return stack at function call time so that, when an instruction is fetched to return from the function, before branching by obtaining a return address from memory is processed, the return address from the return stack is obtained for use in predicting the address to be fetched next.
Also, one indirect branching-related technology for branch prediction involves predicting the branch destination by the programmer designating key information that contributes to indirect branching results and using single-purpose implicit operation instructions within the program (see Patent Literature 1).